package leecode

func reversePairs(nums []int) int {
	length := len(nums)
	if length < 2 {
		return 0
	}
	left := 0
	right := length - 1
	return process(nums, left, right)
}

func process(nums []int, left int, right int) int {
	if left == right {
		return 0
	}
	mid := left + (right-left)/2
	var leftCount = process(nums, 0, mid)
	rightCount := process(nums, mid+1, right)
	return leftCount + rightCount + merge170(nums, left, mid, right)
}

func merge170(nums []int, left int, mid int, right int) int {
	var res int
	temp := make([]int, right-left+1)
	p1, p2 := left, mid+1 // 左右指针
	i := 0

	for p1 <= mid && p2 <= right {
		if nums[p1] <= nums[p2] {
			temp[i] = nums[p1]
			res += p2 - (mid + 1)
			p1++
		} else {
			temp[i] = nums[p2]
			p2++
		}
		i++
	}

	for ; p1 <= mid; p1++ {
		temp[i] = nums[p1]
		res += right - (mid + 1) + 1
		i++
	}

	for ; p2 <= right; p2++ {
		temp[i] = nums[p2]
		i++
	}

	for i, val := range temp {
		nums[left+i] = val
	}

	return res
}
